#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

namespace YX
{
    template<typename W>
    struct BinaryTreeNode 
    {
        struct BinaryTreeNode<W>* _left; 
        struct BinaryTreeNode<W>* _right;
        W _w;

        BinaryTreeNode(const W& w)
            :_left(nullptr)
            ,_right(nullptr)
            ,_w(w)
        {

        }
    };

    template<class W,bool B=true>
    class BinaryTree 
    {
        typedef struct BinaryTreeNode<W> Node;
        private:
            Node* _root;
            unordered_map<W,int> _index;

            // 前序构建
            Node* prev_BinaryTree(const vector<W>& prevorder,const vector<W>& inorder,int p_left,int p_right,int i_left,int i_right)
            {
                if(p_left>p_right)
                {
                    return nullptr;
                }
                
                int root_index=_index[prevorder[p_left]];

                Node* newNode=new Node(prevorder[p_left]);

                newNode->_left=prev_BinaryTree(prevorder,inorder,p_left+1,p_left+(root_index-i_left),i_left,root_index-1);
                newNode->_right=prev_BinaryTree(prevorder,inorder,p_right-(i_right-root_index)+1,p_right,root_index+1,i_right);

                return newNode;
            }

            // 后序构建
            Node* post_BinaryTree(const vector<W>& postorder,const vector<W>& inorder,int p_left,int p_right,int i_left,int i_right)
            {
                if(p_left>p_right)
                {
                    return nullptr;
                }
                
                int root_index=_index[postorder[p_right]];

                Node* newNode=new Node(postorder[p_right]);

                newNode->_left=post_BinaryTree(postorder,inorder,p_left,p_left+(root_index-i_left)-1,i_left,root_index-1);
                newNode->_right=post_BinaryTree(postorder,inorder,p_right-(i_right-root_index),p_right-1,root_index+1,i_right);

                return newNode;
            }

            void _PrevOrder(Node* root)
            {
                if(root==nullptr)
                {
                    return;
                }
                
                cout<<root->_w<<" ";
                _PrevOrder(root->_left);
                _PrevOrder(root->_right);
            }

            void _InOrder(Node* root)
            {
                if(root==nullptr)
                {
                    return;
                }
                
                _InOrder(root->_left);
                cout<<root->_w<<" ";
                _InOrder(root->_right);
            }

            int _NodeSize(Node* root)
            {
                if(root==nullptr)
                {
                    return 0;
                }

                return _NodeSize(root->_left)+_NodeSize(root->_right)+1;
            }

            int _LeafNodeSize(Node* root)
            {
                if(root==nullptr)
                {
                    return 0;
                }

                if(root->_left==nullptr&&root->_right==nullptr)
                {
                    return 1;
                }
                
                return _LeafNodeSize(root->_left)+_LeafNodeSize(root->_right);

            }

            int _Depth(Node* root)
            {
                if(root==nullptr)
                {
                    return 0;
                }

                int leftD=_Depth(root->_left);
                int rightD=_Depth(root->_right);

                return (leftD>rightD?leftD:rightD)+1;
            }

            int _LevelNodeSize(Node* root,int k)
            {
                if(root==nullptr)
                {
                    return 0;
                }

                if(k==1)
                {
                    return 1;
                }

                return _LevelNodeSize(root->_left,k-1)+_LevelNodeSize(root->_right,k-1);
                
            }

            Node* _CopyBinaryTree(const Node* root)
            {
               if(root==nullptr)
               {    
                   return nullptr;
               }
                
               Node* newNode=new Node(root->_w);

               newNode->_left=_CopyBinaryTree(root->_left);
               newNode->_right=_CopyBinaryTree(root->_right);

               return newNode;
            }

            void _Destroy(Node* root)
            {
                if(root==nullptr)
                {
                    return;
                }

                _Destroy(root->_left);
                _Destroy(root->_right);

                delete root;
            }

            int _DegreeTwoSize(Node* root)
            {
                if(root==nullptr)
                {
                    return 0;
                }

                int ret=0;

                if(root->_left!=nullptr && root->_right!=nullptr)
                {
                    ret=1;
                }

                return _DegreeTwoSize(root->_left)+_DegreeTwoSize(root->_right)+ret;
            }

            int _DegreeOneSize(Node* root)
            {
                if(root==nullptr)
                {
                    return 0;
                }

                int ret=0;

                if((root->_left!=nullptr&&root->_right==nullptr)||(root->_left==nullptr&&root->_right!=nullptr))
                {
                    ret=1;
                }
                return _DegreeOneSize(root->_left)+_DegreeOneSize(root->_right)+ret;
            }

        public:
            // 构造函数
            BinaryTree(const vector<W>& order,const vector<W>& inorder)
                :_root(nullptr)
            {
                
                int n=inorder.size();

                _index.clear();

                for(int i=0;i<n;i++)
                {
                    _index[inorder[i]]=i;
                }

                if(B==true)
                {
                   _root=prev_BinaryTree(order,inorder,0,n-1,0,n-1);
                }
                else if(B==false) 
                {
                    _root=post_BinaryTree(order,inorder,0,n-1,0,n-1);
                }

            }

            BinaryTree(const BinaryTree<W>& tree)
                :_root(nullptr)
            {
                _root=_CopyBinaryTree(tree._root);
            }

            BinaryTree<W>& operator=(BinaryTree<W> tree)
            {
                std::swap(_root,tree._root);
            }

            ~BinaryTree()
            {
                _Destroy(_root);
                _root=nullptr;
            }

            // 求二叉树的结点个数
            int NodeSize()
            {
                return _NodeSize(_root);
            }

            // 求叶子结点个数
            int LeafNodeSize()
            {
                return _LeafNodeSize(_root);
            }

            // 求二叉树的高度
            int Depth()
            {
                return _Depth(_root);
            }

            int LevelNodeSize(int k)
            {
                return _LevelNodeSize(_root,k);
            }

            // 前序遍历
            void PrevOrder()
            {
                _PrevOrder(_root);
                cout<<endl;
            }

            // 中序遍历
            void InOrder()
            {
                _InOrder(_root);
                cout<<endl;
            }

            // 度为二的结点
            int DegreeTwoSize()
            {
                return _DegreeTwoSize(_root);
            }

            // 度为一的结点
            int DegreeOneSize()
            {
                return _DegreeOneSize(_root);
            }

    };

    void TestBinaryTree()
    {
        vector<int> p={3,9,20,15,7};
        vector<int> i={9,3,15,20,7};
        
        BinaryTree<int> tree(p,i);

        //tree.PrevOrder();

        //vector<string> p={"3","9","20","15","7"};
        //vector<string> i={"9","3","15","20","7"};
        //vector<char> p={'A','B','D','F','C','E','G','H'};
        //vector<char> i={'B','F','D','A','G','E','H','C'};
        
        //BinaryTree<string> tree(p,i);

        //BinaryTree<string> copy(tree);
        //tree=copy;
        //tree.InOrder();
        //tree.PrevOrder();
        
        printf("NodeSize:%d\n",tree.NodeSize());
        printf("LeafNodeSize:%d\n",tree.LeafNodeSize());
        printf("Depth:%d\n",tree.Depth());
        printf("LevelNodeSize:%d\n",tree.LevelNodeSize(2));
        printf("DegreeOneSize:%d\n",tree.DegreeOneSize());
        printf("DegreeTwoSize:%d\n",tree.DegreeTwoSize());
    }


};
